#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

void test1(){
    set<int> s1;
    s1.insert(3);
    s1.insert(1);
    s1.insert(4);
    s1.insert(2);
    s1.insert(1);
    s1.insert(3);
    set<int>::iterator it = s1.begin();
    while (it != s1.end()){
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

void test2(){
    set<int> s1;
    s1.insert(3);
    s1.insert(1);
    s1.insert(4);
    s1.insert(2);
    s1.insert(1);
    s1.insert(3);
    int x;
    while (cin >>  x){
        if (s1.count(x))
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }
}

void test3(){
    multiset<int> s1;
    s1.insert(3);
    s1.insert(1);
    s1.insert(4);
    s1.insert(2);
    s1.insert(1);
    s1.insert(3);
    s1.insert(1);

    auto it = s1.begin();
    while (it != s1.end()){
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    auto ret = s1.find(1);
    while (ret != s1.end() && *ret == 1){
        cout << *ret << " ";
        ++ret;
    }
    cout << endl;
    cout << s1.count(1) << endl;
    cout << s1.count(2) << endl;
}

void test4(){
    map<string, string> dict;
    dict.insert(make_pair("increase", "decrease"));
    dict.insert(make_pair("greater", "less"));
    dict.insert(make_pair("forward", "backward"));
    auto dit = dict.begin();
    while (dit != dict.end()){
        cout << (*dit).first << ":" << (*dit).second << endl;
        ++dit;
    }
    cout << endl;
}

void test5(){
    map<string, string> dict;
    dict.insert(make_pair("increase", "decrease"));
    dict.insert(make_pair("greater", "less"));
    dict.insert(make_pair("forward", "backward"));
    dict.insert(make_pair("forward", "go"));

    dict["left"];
    dict["right"] = "left";
    dict["forward"] = "Backward";

    cout << dict["forward"] << endl;

    auto dit = dict.begin();
    while (dit != dict.end()){
        cout << dit->first << ":" << dit->second << endl;
        ++dit;
    }
    cout << endl;
}

void test6(){
    string arr[] = {"apple", "watermelon", "banana", "apple", "apple", "watermelon", "apple"};
    map<string, int> countMap;
    for (auto& e : arr) {
        countMap[e]++;
    }
    for (auto& kv : countMap) {
        cout << kv.first << ":" << kv.second << endl;
    }
}

//692. 前K个高频单词
//https://leetcode.cn/problems/top-k-frequent-words/

//法1：先map计数，再直接stable_sort按value排序
/*
class Solution {
public:
    struct Compare{
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2){
            return kv1.second > kv2.second;
        }
    };

    static vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countMap;
        for (auto& str : words) {
            countMap[str]++;
        }
        vector<pair<string, int>> v(countMap.begin(), countMap.end());
        stable_sort(v.begin(), v.end(),Compare());
        vector<string> ret;
        for (int i = 0; i < k; ++i) {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};
*/

//修改sort,使其稳定排序
/*
class Solution {
public:
    struct Compare{
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2){
            return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);
        }
    };

    static vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countMap;
        for (auto& str : words) {
            countMap[str]++;
        }
        vector<pair<string, int>> v(countMap.begin(), countMap.end());
        sort(v.begin(), v.end(),Compare());
        vector<string> ret;
        for (int i = 0; i < k; ++i) {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};
*/

//利用multiset构造时排序
/*
class Solution {
public:
    struct Compare{
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)const{
            return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);
        }
    };

    static vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countMap;
        for (auto& str : words) {
            countMap[str]++;
        }
        multiset<pair<string, int>,Compare> sortSet(countMap.begin(), countMap.end());
        vector<string> ret;
        auto it = sortSet.begin();
        while (k--){
            ret.push_back(it->first);
            ++it;
        }
        return ret;
    }
};
*/

//349. 两个数组的交集
//https://leetcode.cn/problems/intersection-of-two-arrays/

/*
class Solution {
public:
    static vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());
        auto it1 = s1.begin();
        auto it2 = s2.begin();
        vector<int> v;
        while (it1 != s1.end() && it2 != s2.end()){
            if (*it1 > *it2)
                ++it2;
            else if (*it1 < *it2)
                ++it1;
            else{
                v.push_back(*it1);
                ++it1;
                ++it2;
            }
        }
        return v;
    }
};
*/

class Solution {
public:
    static vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;
        /* 由于输出的元素唯一不重复因此可以将nums1转化为unordered_set哈希表 */
        unordered_set<int> nums1_set(nums1.begin(),nums1.end());
        for(int & i : nums2){
            /* 判断nums1_set中是否有nums2的元素，若有将此值插入到result */
            if(nums1_set.find(i) != nums1_set.end())
                result.insert(i);
        }
        return vector<int> (result.begin(),result.end());
    }
};


int main() {
    //test6();
    return 0;
}
